﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Auxiliaries
{
    /// <summary>
    /// Provides means to calculate an arithmetic expression in infix notation (string)
    /// </summary>
    public static class Calculator
    {
        /// <summary>
        /// Possible type of tokens
        /// </summary>
        enum TokenType
        {
            operand,
            operation
        }
        /// <summary>
        /// Supported arithmetic operatiors
        /// </summary>
        enum Operators
        {
            INVALID = -1,
            PLUS,
            MINUS,
            MULTIPLY,
            DIVIDE,
            POWER,
            PARENTHESIS_OPEN,
            PARENTHESIS_CLOSE,
            LESS_THAN,
            GREATER_THAN,
            EQUAL,
            DIFFERENT,
            LESS_THAN_OR_EQUAL,
            GREATER_THAN_OR_EQUAL,
            LEFT_SHIFT,
            RIGHT_SHIFT
        }
        /// <summary>
        /// Operator priority / order of execution
        /// </summary>
        enum OperatorPrecednce
        {
            INVALID,
            LESS,
            EQUAL,
            GREATER
        }
        /// <summary>
        /// Returns the relative operator precedence level
        /// </summary>
        /// <param name="op">Evaluated operator</param>
        /// <returns>Relative precedence level</returns>
        static int OperatorPrecedenceLevel(Operators op)
        {
            switch (op)
            {
                case Operators.GREATER_THAN:
                case Operators.GREATER_THAN_OR_EQUAL:
                case Operators.LESS_THAN:
                case Operators.LESS_THAN_OR_EQUAL:
                case Operators.EQUAL:
                    return 0;
                case Operators.LEFT_SHIFT:
                case Operators.RIGHT_SHIFT:
                    return 1;
                case Operators.MINUS:
                case Operators.PLUS:
                    return 2;
                case Operators.MULTIPLY:
                case Operators.DIVIDE:
                    return 3;
                case Operators.POWER:
                    return 4;
                case Operators.PARENTHESIS_OPEN:
                    return 5;
                default:
                    return -1;
            }
        }
        /// <summary>
        /// Compares operator precedence of op1 to op2
        /// </summary>
        /// <param name="op1">Operator</param>
        /// <param name="op2">Operator</param>
        /// <returns>op1 precedence compared to op2</returns>
        static OperatorPrecednce OperatorPrecednceCompare(Operators op1, Operators op2)
        {
            
            int op1Lvl = OperatorPrecedenceLevel(op1);
            int op2Lvl = OperatorPrecedenceLevel(op2);

            if (op1Lvl == -1 || op2Lvl == -1 || op1 == Operators.PARENTHESIS_OPEN)
                return OperatorPrecednce.INVALID;
            else if (op1Lvl > op2Lvl)
                return OperatorPrecednce.GREATER;
            else if (op1Lvl < op2Lvl)
                return OperatorPrecednce.LESS;
            else
                return OperatorPrecednce.EQUAL;
        }

        /// <summary>
        /// Operand and operator tokens used by the calculator
        /// </summary>
        class CalcToken
        {
            public TokenType tType;

            public Operators opType;

            public Int64 val;

            public CalcToken(TokenType type, Int64 iVal)
            {
                tType = type;
                val = iVal;
                opType = Operators.INVALID;
            }

            public CalcToken(TokenType type, Operators iOpType)
            {
                tType = type;
                opType = iOpType;
            }

            public override string ToString()
            {
                if (tType == TokenType.operand)
                    return val.ToString();
                else if (tType == TokenType.operation)
                    return opType.ToString();
                else
                    return base.ToString();
            }
        }
        /// <summary>
        /// Parses an integer from a string - can be hex format string
        /// </summary>
        /// <param name="scrWord">string value to parse</param>
        /// <returns>integer result</returns>
        public static Int64 ParseInteger(string scrWord)
        {
            Int64 intVal;
            if (!Int64.TryParse(scrWord, out intVal))
            {
                UInt64 tmpVal;
                if (!HEX_converter.ToBinary(scrWord, out tmpVal))
                    throw new Exception("Cannot parse " + scrWord + " to an integer value!");
                else
                    intVal = (Int64)tmpVal;
            }

            return intVal;
        }
        /// <summary>
        /// Parses an unsigned integer from a string - can be hex format string
        /// </summary>
        /// <param name="scrWord">string value to parse</param>
        /// <returns>unsigned integer result</returns>
        public static UInt64 ParseUInteger(string scrWord)
        {
            UInt64 intVal;
            if (!UInt64.TryParse(scrWord, out intVal))
            {
                UInt64 tmpVal;
                if (!HEX_converter.ToBinary(scrWord, out tmpVal))
                    throw new Exception("Cannot parse " + scrWord + " to an integer value!");
                else
                    intVal = (UInt64)tmpVal;
            }

            return intVal;
        }
        /// <summary>
        /// Checks if a character is an arithmetic symbol (of interest)
        /// </summary>
        /// <param name="str">Character to test</param>
        /// <returns>Bool result</returns>
        static public bool StringIsArithmeticOperation(string str)
        {
            if (str == "+" ||
                str == "-" ||
                str == "*" ||
                str == "/" ||
                str == "(" ||
                str == ")" ||
                str == "^" ||
                str == "=" ||
                str == "<" ||
                str == ">" ||
                str == "==" ||
                str == "!=" ||
                str == "<=" ||
                str == ">=" ||
                str == "<<" ||
                str == ">>")
                return true;
            else
                return false;
        }
        /// <summary>
        /// Checks if a character is a word separator
        /// </summary>
        /// <param name="ch">Character to test</param>
        /// <returns>Bool result</returns>
        static public bool CharIsWordSeparator(char ch)
        {
            if (ch == '\n' ||
                ch == ' ' ||
                ch == '\t')
                return true;
            else
                return false;
        }
        /// <summary>
        /// Converts a character to operator enumeration
        /// </summary>
        /// <param name="str">Character to concert</param>
        /// <returns>Corresponding operator</returns>
        static Operators StringToOperator(string str)
        {
            switch (str)
            {
                case "/":
                    return Operators.DIVIDE;
                case "*":
                    return Operators.MULTIPLY;
                case "+":
                    return Operators.PLUS;
                case "-":
                    return Operators.MINUS;
                case "(":
                    return Operators.PARENTHESIS_OPEN;
                case ")":
                    return Operators.PARENTHESIS_CLOSE;
                case "^":
                    return Operators.POWER;
                case "<":
                    return Operators.LESS_THAN;
                case ">":
                    return Operators.GREATER_THAN;
                case "==":
                    return Operators.EQUAL;
                case "!=":
                    return Operators.DIFFERENT;
                case "<=":
                    return Operators.LESS_THAN_OR_EQUAL;
                case ">=":
                    return Operators.GREATER_THAN_OR_EQUAL;
                case "<<":
                    return Operators.LEFT_SHIFT;
                case ">>":
                    return Operators.RIGHT_SHIFT;
                default:
                    return Operators.INVALID;
            }
        }
        /// <summary>
        /// Reads a complete word from a string - word defined by two spaces
        /// </summary>
        /// <param name="index_pos">The position within the string where to start the reading</param>
        /// <param name="line">The string which is to be read</param>
        /// <returns>The word extratced from the string</returns>
        static string ReadItem(ref int index_pos, string line)
        {
            //The parsed word result
            String word = "";

            if (index_pos > -1 && line.Length > 0)
            {
                while (index_pos < line.Length && (CharIsWordSeparator(line[index_pos])))
                    index_pos++;

                while (index_pos < line.Length && (StringIsArithmeticOperation(line.Substring(index_pos, 1)) || StringIsArithmeticOperation(line.Substring(index_pos, 2))))
                {
                    //Special case handling - as the whole function is working
                    //on single character basis and there are three two character
                    // arithmetic operations, hence this if....
                    if (index_pos < line.Length - 1 && StringIsArithmeticOperation(line.Substring(index_pos + 1, 1)) && StringIsArithmeticOperation(line.Substring(index_pos, 2)))
                    {
                        index_pos += 2;
                        return line.Substring(index_pos - 2, 2);
                    }
                    else
                    {
                        index_pos++;
                        return "" + line[index_pos - 1];
                    }
                }
                while (index_pos < line.Length && !CharIsWordSeparator(line[index_pos]))
                {
                    word += line[index_pos++];
                }
            }
            return word;
        }
        /// <summary>
        /// Converts an arithmetic expression in infix notation to a list of postfixed tokens
        /// </summary>
        /// <param name="infix">Arithmetic expression</param>
        /// <returns>Postfixed token list</returns>
        static List<CalcToken> ConvertInfix2PostfixTokenized(string infix)
        {
            int indxPos = 0;
            List<CalcToken> postfixed = new List<CalcToken>();
            Stack<CalcToken> operatorStack = new Stack<CalcToken>();
            bool expecOp = false;
            bool parseNeg = false;

            while (indxPos < infix.Length)
            {
                string item = ReadItem(ref indxPos, infix);

                if (item.Length == 0)
                    continue;

                if (StringIsArithmeticOperation(item))
                {
                    if (expecOp || item != "-")
                    {
                        if (item != "(" && item != ")")
                            expecOp = !expecOp;

                        CalcToken newToStack = new CalcToken(TokenType.operation, StringToOperator(item));
                        if (newToStack.opType != Operators.PARENTHESIS_OPEN &&
                            operatorStack.Count > 0)
                        {
                            CalcToken topStack = operatorStack.Peek();

                            if (newToStack.opType == Operators.PARENTHESIS_CLOSE)
                            {
                                while (topStack.opType != Operators.PARENTHESIS_OPEN)
                                {
                                    postfixed.Add(operatorStack.Pop());
                                    topStack = operatorStack.Peek();
                                }
                                operatorStack.Pop();
                            }
                            else
                            {

                                while (operatorStack.Count > 0 && (OperatorPrecednceCompare(topStack.opType, newToStack.opType) == OperatorPrecednce.GREATER ||
                                        OperatorPrecednceCompare(topStack.opType, newToStack.opType) == OperatorPrecednce.EQUAL))
                                {
                                    postfixed.Add(operatorStack.Pop());
                                    if (operatorStack.Count > 0)
                                        topStack = operatorStack.Peek();
                                }

                                operatorStack.Push(newToStack);
                            }
                        }
                        else
                        {
                            operatorStack.Push(newToStack);
                        }
                    }
                    else
                    {
                        parseNeg = true;
                    }
                }
                else
                {
                    expecOp = !expecOp;
                    if (parseNeg)
                    {
                        parseNeg = false;
                        item = "-" + item;
                    }
                    postfixed.Add(new CalcToken(TokenType.operand, Int64.Parse(item)));
                }
            }

            while (operatorStack.Count > 0)
            {
                postfixed.Add(operatorStack.Pop());
            }

            return postfixed;
        }
        /// <summary>
        /// Evalueates an expression in postfixed notation token list
        /// </summary>
        /// <param name="postfix">List of postfixed tokens</param>
        /// <returns>result</returns>
        static Int64 Calculate(List<CalcToken> postfix)
        {
            try
            {
                //Do while there is only one integer - the result
                while (postfix.Count > 1)
                {
                    int itr = 0;

                    //Find two operands with an immidiate operator to process
                    while (!(postfix[itr].tType == TokenType.operand && postfix[itr + 1].tType == TokenType.operand && postfix[itr + 2].tType == TokenType.operation))
                        itr++;
                    //Calculate based on operation type
                    switch (postfix[itr + 2].opType)
                    {
                        case Operators.PLUS:
                            postfix[itr].val += postfix[itr + 1].val;
                            break;
                        case Operators.MINUS:
                            postfix[itr].val -= postfix[itr + 1].val;
                            break;
                        case Operators.MULTIPLY:
                            postfix[itr].val *= postfix[itr + 1].val;
                            break;
                        case Operators.DIVIDE:
                            postfix[itr].val /= postfix[itr + 1].val;
                            break;
                        case Operators.POWER:
                            Int64 val = postfix[itr].val;
                            for (int i = 1; i < postfix[itr + 1].val; i++)
                            {
                                postfix[itr].val *= val;
                            }
                            break;
                        case Operators.EQUAL:
                            if (postfix[itr].val == postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.DIFFERENT:
                            if (postfix[itr].val != postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.LESS_THAN:
                            if (postfix[itr].val < postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.LESS_THAN_OR_EQUAL:
                            if (postfix[itr].val <= postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.GREATER_THAN:
                            if (postfix[itr].val > postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.GREATER_THAN_OR_EQUAL:
                            if (postfix[itr].val >= postfix[itr + 1].val)
                                postfix[itr].val = 1;
                            else
                                postfix[itr].val = 0;
                            break;
                        case Operators.LEFT_SHIFT:
                            postfix[itr].val = (postfix[itr].val << (Int32)postfix[itr + 1].val);
                            break;
                        case Operators.RIGHT_SHIFT:
                            postfix[itr].val = (postfix[itr].val >> (Int32)postfix[itr + 1].val);
                            break;
                    }
                    //Remove second operand
                    postfix.RemoveAt(itr + 1);
                    //Remove operation
                    postfix.RemoveAt(itr + 1);
                }
                if (postfix.Count == 1)
                    return postfix[0].val;
                else
                    return 0;//Error?! Wrong parsing?!... tz tz
            }
            catch (Exception ex)
            {
                throw new Exception("Calculation error!\n" + ex.Message);
            }
        }

        /// <summary>
        /// Evalueates an expression in infixed notation string
        /// </summary>
        /// <param name="infix">Infix notation arithmetic expression</param>
        /// <returns>result</returns>
        public static Int64 Calculate(string infix)
        {
            return Calculate(ConvertInfix2PostfixTokenized(infix));
        }
    }
}
